/*
 * @lc app=leetcode.cn id=138 lang=typescript
 *
 * [138] 复制带随机指针的链表
 */

// @lc code=start

// Definition for Node.
/* class Node {
  val: number;
  next: Node | null;
  random: Node | null;
  constructor(val?: number, next?: Node, random?: Node) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
    this.random = random === undefined ? null : random;
  }
} */

function copyRandomList(head: Node | null): Node | null {
  if (head === null) return null;

  // 复制每个节点，将复制的节点插入到当前节点后面
  let p = head;
  while (p !== null) {
    const node = new Node(p.val, p.next, p.random);
    p.next = node;
    p = node.next;
  }
  // 更新复制节点的random节点
  p = head.next;
  while (p !== null) {
    p.random = p.random ? p.random.next : null;
    p = p.next ? p.next.next : null;
  }

  // 将复制节点拆出来
  const ans = head.next;
  let q = head.next;
  p = head;
  while (q !== null) {
    p.next = q.next;
    p = p.next;
    q.next = p ? p.next : null;
    q = q.next;
  }

  return ans;
}
// @lc code=end
